package leetcode101.divide_conquer;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code3
 * @Description TODO
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-23 14:21
 */
public class Code3 {
    public static void main(String[] args) {
        int[] nums = new int[]{3, 1, 5, 8};
        System.out.println(maxCoins(nums));
    }

    public static int maxCoins(int[] nums) {
        int[] balloons = new int[nums.length + 2];
        System.arraycopy(nums, 0, balloons, 1, nums.length);
        balloons[0] = 1;
        balloons[balloons.length - 1] = 1;
        /*
        dp[i][j] 代表打爆了(i, j)区间气球的最大得分
         */
        int[][] dp = new int[balloons.length][balloons.length];

        /*
        i控制左边界
         */
        for (int i = balloons.length - 3; i > -1; i--) {
            for (int j = i + 2; j < balloons.length; j++) {
                for (int k = i + 1; k < j; k++) {
                    int shotK = balloons[i] * balloons[k] * balloons[j];
                    int shotLeft = dp[i][k];
                    int shotRight = dp[k][j];
                    dp[i][j] = Math.max(dp[i][j], shotK + shotLeft + shotRight);
                }
            }
        }
        return dp[0][balloons.length - 1];
    }
}
/*
为什么能用dp解决呢？
想，是不是我每一次打爆不同的气球都会对我后面的结果产生相应的影响呢？
那既然前面的动作会对后面的结果产生影响的话那么就应该使用动态规划来解决
那么如何设置状态转移方程呢
这道题用范围dp会更好一点
dp[i][j]代表了我在开区间 (i, j)中打爆所有气球获得的最高分数
那么dp[i][j] = Max{dp[i][k] + dp[k][j] + score[i] * score[k] * score[j]} 其中 i + 1 <= k <= j - 1
比如dp[2][5] = Max{dp[2][3] + dp[3][5] + score[2] * score[3] * score[5],
                  dp[2][4] + dp[4][5] + score[2] * score[4] * score[5]
                  }
通过以上的状态转移方程我们可以看到，第 i 行的数据要用到第 i + 1 行的数据 所以我们行要倒着赋值
对于列的话 第 j 列的数据要用到第 j - 1列的数据，所以列要正着赋值
最后由于是开区间，返回dp[0][balloons.length - 1]
 */